package leetcode3;

import java.util.*;
  class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }


public class Day8 {



    public static void main(String[] args) {

    }



    public List<List<Integer>> levelOrder(TreeNode root) {
        //1.先将头结点放入队列
        //2.遍历队列，记录每层的结点个数
        //3.记录结果和将下一轮节点存入队列中
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null) return ret;
        queue.add(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while (size-- != 0) {
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                //将左右子树入队
                if(cur.right!=null) queue.add(cur.right);
                if(cur.left!=null) queue.add(cur.left);

            }
            ret.add(tmp);
        }
        return ret;
    }

    //最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return root;
        //1.判断当前root是否为q|p中的一个
        //2.递归左子树
        //3.判断右子树

        if(root == p || root == q) return root;
        TreeNode leftNode =  lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode =  lowestCommonAncestor(root.right,p,q);

        if(leftNode != null && rightNode != null) { //p和q分别在root的两侧
            return root;
        }else if(leftNode!=null && rightNode==null) { //在同一侧，公共祖先为左
            return leftNode;
        }else {
            return rightNode;
        }
    }


    //判断链表是否有环
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
}
